from typing import *


class Solution:
    def rootCount(
        self, edges: List[List[int]], guesses: List[List[int]], k: int
    ) -> int:
        s = set()
        for u, v in guesses:
            s.add((u, v))

        n = len(edges) + 1

        nexts = [[] for _ in range(n)]
        for a, b in edges:
            nexts[a].append(b)
            nexts[b].append(a)

        yes = [0] * n
        no = [0] * n

        def dfs(root, parent):
            yeah = nope = 0
            for nxt in nexts[root]:
                if nxt != parent:
                    if (root, nxt) in s:
                        yeah += 1
                    if (nxt, root) in s:
                        nope += 1
                    a, b = dfs(nxt, root)
                    yeah += a
                    nope += b
            yes[root] = yeah
            no[root] = nope
            return yeah, nope

        dfs(0, -1)
        ans = 0

        def dfs2(root, parent):
            nonlocal ans
            if yes[root] >= k:
                ans += 1
            for nxt in nexts[root]:
                if nxt != parent:
                    a, b = yes[root], no[root]
                    c, d = yes[nxt], no[nxt]
                    yes[root] -= yes[nxt]
                    no[root] -= no[nxt]
                    if (root, nxt) in s:
                        yes[root] -= 1
                        no[nxt] += 1
                    if (nxt, root) in s:
                        no[root] -= 1
                        yes[nxt] += 1
                    yes[nxt] += yes[root]
                    no[nxt] += no[root]

                    dfs2(nxt, root)

                    yes[root], no[root] = a, b
                    yes[nxt], no[nxt] = c, d

        dfs2(0, -1)
        return ans


s = Solution()
print(
    s.rootCount(
        edges=[[0, 1], [1, 2], [1, 3], [4, 2]],
        guesses=[[1, 3], [0, 1], [1, 0], [2, 4]],
        k=3,
    )
)
